package arrays;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 题目： 数组中最小的 K 个数
 *
 * @Author Gavin
 * @date 2022.08.06 15:52
 */
public class array_23 {
    /**
     * 第一种方法：使用一个大小为k的大顶堆（默认是小顶堆[从小到大输出]）
     */
    //O(NlogK) + O(K)
    public ArrayList<Integer> solution(int[] nums, int k) {
        if (k > nums.length || k <= 0)
            return new ArrayList<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int num : nums) {
            maxHeap.add(num);
            if (maxHeap.size() > k)
                maxHeap.poll();
        }
        return new ArrayList<>(maxHeap);
    }
    /**
     * 第二种方法：快速排序
     */
    //利用快速排序
    public ArrayList<Integer> solution_2(int[] nums, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        getByFastAsc(nums);//传递的是引用，所以nums里面已经排序了
        for (int i = 0; i < k; i++) {
            result.add(nums[i]);
        }
        return result;
    }

    public void getByFastAsc(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {//控制循环次数
            int min = i;//最小索引
            for (int j = i + 1; j < arr.length; j++) {//从无序区选取最小的记录
                if (arr[min] > arr[j]) {//如果最小数索引的数比后面的数大就和该数交换索引
                    min = j;//交换索引，循环重复后得出最小的数的索引
                }
            }
            if (min != i) {//如果最小数的索引和一开始引用的数的索引不想等，那么就做一个替换。
                int temp = arr[i];//把一开始引用的数传给中间介质，也就是较大值
                arr[i] = arr[min];//把最小数传到一开始定位的位置
                arr[min] = temp;//把中间介质传给最小数，把大值赋值给min位置
            }
        }
    }
}
